package airthmetic.exercise.queue;

import java.util.Deque;
import java.util.LinkedList;

public class _239_滑动窗口的最大值 {
    public static int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || nums.length < k){
            return null;
        }

        int[] res = new int[nums.length - k + 1];
        int current = 0;
        Deque<Integer> queue = new LinkedList<>();
        for (int i=0; i < nums.length; i++){
            while(!queue.isEmpty() && nums[queue.peekLast()] <=nums[i]){
                queue.pollLast();
            }
            queue.offerLast(i);

            if (i - queue.peekFirst() >= k){
                queue.pollFirst();
            }
            if (i >= k-1){
                res[current++] = nums[queue.peekFirst()];
            }

        }
        return res;

    }


    public static int[] maxSlidingWindow2(int[] nums, int k) {
        if(nums == null || nums.length < k){
            return new int[]{};
        }
        Deque<Integer> queue = new LinkedList();
        int[] res = new int[nums.length - k + 1];
        int current = 0;
        for(int i=0; i<nums.length; i++){
            while(!queue.isEmpty() && nums[queue.peekLast()] <= nums[i]){
                queue.pollLast();
            }
            queue.offerLast(i);

            if(i - queue.peekFirst()  >= k){
                queue.pollFirst();
            }

            if(i >= k - 1){
                res[current++] = queue.peekFirst();
            }
        }
        return res;
    }

    public static void main(String[] args) {
        //        int[] ints = maxSlidingWindow2(nums, k);
//        int[] nums = {7, 2, 4};
//        int k = 2;


        int[] nums = {1};
        int k = 1;

        int[] ints = maxSlidingWindow2(nums, k);
        for (int i = 0; i < ints.length; i++) {
            System.out.println(ints[i]);
        }
    }
}
